#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import typing

class Solution:
    def __init__(self) -> None:
        self.count = 0
        self.nums = list()

    def findTarget(self, target: int, sum: int, index: int):
        if index == len(self.nums):
            if sum == target:
                self.count += 1
        else:
            self.findTarget(target, sum + self.nums[index], index + 1)
            self.findTarget(target, sum - self.nums[index], index + 1)

    def findTargetSumWays(self, nums: typing.List[int], target: int) -> int:
        self.nums = nums
        self.findTarget(target, 0, 0)
        return self.count

if __name__ == "__main__":
    nums = [
        38, 21, 23, 36, 1, 36, 18, 3, 37, 27, 29, 29, 35, 47, 16, 0, 2, 42, 46,
        6
    ]
    solution = Solution()
    print(solution.findTargetSumWays(nums, 14))